#include "GrafoLA.h"

void creaGrafoN(Grafo &G){
int i;
    for(i=0;i<N;i++)
        crearLista(G[i]);
}

void agregaArista(Grafo &G, int vert1, int vert2){
    insBackLista(G[vert1],vert2);
    if(vert1!=vert2)                //Si es un lazo inserto solo una vez la arista
        insBackLista(G[vert2],vert1);
}

int gradoVertice(Grafo G, int vertice){
int grado=0;
    if(perteneceRLista(G[vertice],vertice))     //Tiene lazo, entonces son dos extremos de aristas
        grado++;
    grado=grado+largoLista(G[vertice]);
    return grado;
}

void desplegaVerticesAdyacentes(Grafo G, int vertice){
    desplegarLista(G[vertice]);
}

bool existeArista(Grafo G, int vert1, int vert2){
    if(perteneceRLista(G[vert1],vert2))
        return true;
    else
        return false;
}

bool esGrafoSimple(Grafo G){
int i=0;
bool simple=true;

    while(i<N&&simple){
        if(perteneceRLista(G[i],i))
            simple=false;
        i++;
    }
    return simple;
}

bool esGrafoCompleto(Grafo G){
int i=0,j;
bool completo=true;

    if(esGrafoSimple(G)){
        while(i<N&&completo){
            for(j=0;j<N;j++){
                if(j!=i)
                    if(!perteneceRLista(G[i],j))
                        completo=false;
            }
            i++;
        }
    }else
        completo=false;
    return completo;
}

//Grafo no vacio
bool esGrafoRegular(Grafo G){
int grado,gradoAux,i=1;
bool regular=true;

    grado=gradoVertice(G,0);

    while(i<N&&regular){
        gradoAux=gradoVertice(G,i);
        if(gradoAux!=grado)
            regular=false;
        i++;
    }
    return regular;
}

bool verticeValido(int V){
    if(V >= N || V < 0 )
        return false;
    else
        return true;
}

void eliminarGrafo(Grafo G){
int i;
    for(i=0;i<N;i++)
        eliminarLista(G[i]);
}

/////////////////////////
///////// AUX   /////////
/////////////////////////

bool esGrafoConexo(Grafo G){
Visitado visitado;
int i;
bool conexo=true;

    for(i=0;i<N;i++)
        visitado[i]=false;

    DFSGrafoConexo(G,0,visitado);

    i=0;
    while(i<N&&conexo){
        if(!visitado[i])
            conexo=false;
        i++;
    }
    return conexo;
}

void DFSGrafoConexo(Grafo G, int verticeActual,Visitado visitado){
visitado[verticeActual] = true;
lista listaAux=G[verticeActual];
    while(listaAux!=NULL){
        if (!visitado[listaAux->entero])
            DFSGrafoConexo(G,listaAux->entero,visitado);
        listaAux=listaAux->sig;
    }
}


/////////////////////////
///////// EJE 1 /////////
/////////////////////////

int cantidadComponentesConexas(Grafo G){
Visitado visitado;
int i,cantComponentes=0, compConexa=0;

    for(i=0;i<N;i++)
        visitado[i]=false;
    i=0;

    while(cantComponentes<N){

        while(visitado[i]&&i<N-1)
            i++;
        compConexa++;
        DFSComponentesConexas(G,i,visitado,cantComponentes);
    }
    return compConexa;
}

void DFSComponentesConexas(Grafo G, int verticeActual,Visitado visitado,int &cantComponentes){
visitado[verticeActual] = true;
lista listaAux=G[verticeActual];
cantComponentes++;

    while(listaAux!=NULL){
        if (!visitado[listaAux->entero]){
            DFSComponentesConexas(G,listaAux->entero,visitado,cantComponentes);
        }

        listaAux=listaAux->sig;
    }
}


/////////////////////////
///////// EJE 2 /////////
/////////////////////////

lista caminoMasLargo(Grafo G){
Visitado visitado;
int i,j;
lista listaCamino,listaAux;
crearLista(listaCamino);
crearLista(listaAux);

    for(i=0;i<N;i++){
        for(j=0;j<N;j++)
            visitado[j]=false;
        DFScaminoMasLargo(G,i,visitado,listaCamino,listaAux);
        crearLista(listaAux);
    }
    eliminarLista(listaAux);
    return listaCamino;
}

void DFScaminoMasLargo(Grafo G, int verticeActual,Visitado visitado,lista &listaCamino,lista &listaAux){

visitado[verticeActual] = true;
insBackLista(listaAux,verticeActual);

lista listaGrafoAux=G[verticeActual];

    while(listaGrafoAux!=NULL){
        if (!visitado[listaGrafoAux->entero])
            DFScaminoMasLargo(G,listaGrafoAux->entero,visitado,listaCamino,listaAux);
        listaGrafoAux=listaGrafoAux->sig;
    }

    if(largoLista(listaAux)>largoLista(listaCamino)){
        eliminarLista(listaCamino);
        listaCamino=copiarLista(listaAux);
    }
    borrarElementoLista(listaAux,verticeActual);
}

/////////////////////////
///////// EJE 3 /////////
/////////////////////////

int desplegarVertices(Grafo G){
Visitado visitado;
int i;
    for(i=0;i<N;i++)
        visitado[i]=false;

    for(i=0;i<N;i++){
        if(!visitado[i])
            DFSdesplegarVertices(G,i,visitado);
    }

}

void DFSdesplegarVertices(Grafo G, int verticeActual,Visitado visitado){

visitado[verticeActual] = true;
lista listaAux=G[verticeActual];

    printf("%d ",verticeActual);

    while(listaAux!=NULL){
        if (!visitado[listaAux->entero]){
            DFSdesplegarVertices(G,listaAux->entero,visitado);
        }
        listaAux=listaAux->sig;
    }

}
